package com.justnow.offer;

/**
 * @author justnow
 * Created on 2020-09-06
 * Description
 *
 * 部分排序
 * 时间限制： 3000MS
 * 内存限制： 655360KB
 * 题目描述：
 * 给定一个整数数组（可能存在重复元素），找出将数组中哪一段连续的数字排序之后，整个数组就会变成有序的（假定这里指的有序为升序）。返回连续的下标[s,e]。如果找不到这样的下标组合，或者数组已经是有序的，则返回[-1,-1]。
 *
 * 例如，数组 [1, 2, 3, 4, 10, 7, 9, 8, 8, 12, 13, 14, 19], 返回[4,8]。数组[1, 2, 3, 4, 5, 6, 7, 8]，返回[-1,-1]。
 *
 *
 * 输入描述
 * 输入是一个整数数组(input为每行为一个数字，第一行数字代表数组大小n，下面n行每行一个数字，代表数组中的元素)
 *
 * 输出描述
 * 输出是一个包含两个元素的整数数组，代表需要调整排序的元素的下标的开始和结束（含）
 *
 *
 * 样例输入
 * 13
 * 1
 * 2
 * 3
 * 4
 * 10
 * 7
 * 9
 * 8
 * 8
 * 12
 * 13
 * 14
 * 19
 * 样例输出
 * 4
 * 8
 *
 *
 */
public class XhsSolution01 {

    static int[] subSort(int[] arr) {
        int[] array = {-1, -1};
        int left = 0, right = 0;

        for (int i = 1; i < arr.length ; i++) {
            if (arr[i] > arr[i - 1]) {
                left = i - 1;
                break;
            }
        }

        for (int i = arr.length - 1; i >= 1; i--) {
            if (arr[i] > arr[i - 1] && arr[i - 1] < arr[left]) {
                right = i - 1;
                break;
            }
        }

        if (left == 0 && right == 0) {
            return array;
        }

        if (left != 0 && right == 0) {
            array[0] = left;
            array[1] = arr.length;
            return array;
        }

        array[0] = left;
        array[1] = right;

        return array;

/*
        for (int i = 1; i < arr.length ; i++) {
            if (arr[i] > arr[i - 1]) {
                left = i - 1;
                break;
            }
        }

        for (int i = arr.length - 1; i > left ; i--) {
            if (arr[i] < arr[left]) {
                right = i;
                break;
            }
        }

        if (left == 0 && right == 0) {
            return array;
        }

        if (left != 0 && right == 0) {
            array[0] = left;
            array[1] = arr.length;
            return array;
        }

        array[0] = left - 1;
        array[1] = right;
*/

        /* 22%
        while (left + 1 < arr.length && arr[left] < arr[left + 1]) {
            left++;
        }

        while (right > 0 && arr[right] > arr[left]) {
            right--;
        }
        array[0] = left - 1;
        array[1] = right;
        */

    }
}
